//344.反转字符串

//编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
//不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

//class Solution {
//public:
//    void reverseString(vector<char>& s) {
//        int n = s.size();
//        for (int left = 0, right = n - 1; left < right; left++, right--) {
//            swap(s[left], s[right]);
//        }
//    }
//};

//125.验证回文串

//如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
//字母和数字都属于字母数字字符。
//给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

//class Solution {
//public:
//    bool isPalindrome(string s) {
//        int left = 0, right = s.size() - 1;
//        while (left < right) {
//            if (!isalnum(s[left])) {
//                left++;
//            }
//            else if (!isalnum(s[right])) {
//                right--;
//            }
//            else if (tolower(s[left]) == tolower(s[right])) {
//                left++;
//                right--;
//            }
//            else {
//                return false;
//            }
//        }
//        return true;
//    }
//};

//1750.删除字符串两端相同字符后的最短长度

//给你一个只包含字符 'a'，'b' 和 'c' 的字符串 s ，你可以执行下面这个操作（5 个步骤）任意次：
//选择字符串 s 一个 非空 的前缀，这个前缀的所有字符都相同。
//选择字符串 s 一个 非空 的后缀，这个后缀的所有字符都相同。
//前缀和后缀在字符串中任意位置都不能有交集。
//前缀和后缀包含的所有字符都要相同。
//同时删除前缀和后缀。
//请你返回对字符串 s 执行上面操作任意次以后（可能 0 次），能得到的 最短长度 。

//class Solution {
//public:
//    int minimumLength(string s) {
//        int n = s.size();
//        int left = 0, right = n - 1;
//        while (left < right && s[left] == s[right]) {
//            char c = s[left];
//            while (left <= right && s[left] == c) {
//                left++;
//            }
//            while (left <= right && s[right] == c) {
//                right--;
//            }
//        }
//        return right - left + 1;
//    }
//};

//2105.给植物浇水 II

//Alice 和 Bob 打算给花园里的 n 株植物浇水。植物排成一行，从左到右进行标记，编号从 0 到 n - 1 。其中，第 i 株植物的位置是 x = i 。
//每一株植物都需要浇特定量的水。Alice 和 Bob 每人有一个水罐，最初是满的 。他们按下面描述的方式完成浇水：
//Alice 按 从左到右 的顺序给植物浇水，从植物 0 开始。Bob 按 从右到左 的顺序给植物浇水，从植物 n - 1 开始。他们 同时 给植物浇水。
//无论需要多少水，为每株植物浇水所需的时间都是相同的。
//如果 Alice / Bob 水罐中的水足以 完全 灌溉植物，他们 必须 给植物浇水。否则，他们 首先（立即）重新装满罐子，然后给植物浇水。
//如果 Alice 和 Bob 到达同一株植物，那么当前水罐中水 更多 的人会给这株植物浇水。如果他俩水量相同，那么 Alice 会给这株植物浇水。
//给你一个下标从 0 开始的整数数组 plants ，数组由 n 个整数组成。其中，plants[i] 为第 i 株植物需要的水量。
//另有两个整数 capacityA 和 capacityB 分别表示 Alice 和 Bob 水罐的容量。返回两人浇灌所有植物过程中重新灌满水罐的 次数 。

//class Solution {
//public:
//    int minimumRefill(vector<int>& plants, int capacityA, int capacityB) {
//        int ans = 0;
//        int a = capacityA, b = capacityB;
//        int i = 0, j = plants.size() - 1;
//        while (i < j) {
//            if (a < plants[i]) {
//                ans++;
//                a = capacityA;
//            }
//            a -= plants[i++];
//            if (b < plants[j]) {
//                ans++;
//                b = capacityB;
//            }
//            b -= plants[j--];
//        }
//        if (i == j && max(a, b) < plants[i]) {
//            ans++;
//        }
//
//        return ans;
//    }
//};

//977.有序数组的平方

//给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

//class Solution {
//public:
//    vector<int> sortedSquares(vector<int>& nums) {
//        int n = nums.size();
//        vector<int> ans(n);
//        int i = 0, j = n - 1;
//        for (int p = n - 1; p >= 0; p--) {
//            int x = nums[i] * nums[i];
//            int y = nums[j] * nums[j];
//            if (x > y) {
//                ans[p] = x;
//                i++;
//            }
//            else {
//                ans[p] = y;
//                j--;
//            }
//        }
//
//        return ans;
//    }
//};

//658.找到 K 个最接近的元素

//给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。
//整数 a 比整数 b 更接近 x 需要满足：
//| a - x | < | b - x | 或者
//| a - x| == |b - x | 且 a < b

//class Solution {
//public:
//    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
//        int right = lower_bound(arr.begin(), arr.end(), x) - arr.begin();
//        int left = right - 1;
//        while (k--) {
//            if (left < 0) {
//                right++;
//            }
//            else if (right >= arr.size()) {
//                left--;
//            }
//            else if (x - arr[left] <= arr[right] - x) {
//                left--;
//            }
//            else {
//                right++;
//            }
//        }
//
//        return vector<int>(arr.begin() + left + 1, arr.begin() + right);
//    }
//};

//1471.数组中的 K 个最强值

//给你一个整数数组 arr 和一个整数 k 。
//设 m 为数组的中位数，只要满足下述两个前提之一，就可以判定 arr[i] 的值比 arr[j] 的值更强：
//| arr[i] - m | > | arr[j] - m|
//|arr[i] - m| == |arr[j] - m | ，且 arr[i] > arr[j]
//请返回由数组中最强的 k 个值组成的列表。答案可以以 任意顺序 返回。
//中位数 是一个有序整数列表中处于中间位置的值。形式上，如果列表的长度为 n ，那么中位数就是该有序列表（下标从 0 开始）中位于((n - 1) / 2) 的元素。
//例如 arr = [6, -3, 7, 2, 11]，n = 5：数组排序后得到 arr = [-3, 2, 6, 7, 11] ，数组的中间位置为 m = ((5 - 1) / 2) = 2 ，中位数 arr[m] 的值为 6 。
//例如 arr = [-7, 22, 17, 3]，n = 4：数组排序后得到 arr = [-7, 3, 17, 22] ，数组的中间位置为 m = ((4 - 1) / 2) = 1 ，中位数 arr[m] 的值为 3 。

//class Solution {
//public:
//    vector<int> getStrongest(vector<int>& arr, int k) {
//        ranges::sort(arr);
//        int n = arr.size(), m = arr[(n - 1) / 2];
//        int l = 0, r = n - 1;
//        vector<int> ans;
//        while (k--) {
//            if (arr[r] - m >= m - arr[l]) {
//                ans.push_back(arr[r]);
//                r--;
//            }
//            else {
//                ans.push_back(arr[l]);
//                l++;
//            }
//        }
//
//        return ans;
//    }
//};

//167.两数之和 II

//给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列  ，
//请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
//以长度为 2 的整数数组[index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
//你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
//你所设计的解决方案必须只使用常量级的额外空间。

//class Solution {
//public:
//    vector<int> twoSum(vector<int>& numbers, int target) {
//        int left = 0, right = numbers.size() - 1;
//        while (true) {
//            int s = numbers[left] + numbers[right];
//            if (s == target) {
//                return { left + 1, right + 1 };
//            }
//            s > target ? right-- : left++;
//        }
//    }
//};

//633.平方数之和

//给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。

//class Solution {
//public:
//    bool judgeSquareSum(int c) {
//        int a = 0, b = sqrt(c);
//        while (a <= b) {
//            if (a * a == c - b * b) {
//                return true;
//            }
//            if (a * a < c - b * b) {
//                a++;
//            }
//            else {
//                b--;
//            }
//        }
//
//        return false;
//    }
//};

//2824.统计和小于目标的下标对数目

//给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 target ，请你返回满足 0 <= i < j < n 且 nums[i] + nums[j] < target 的下标对(i, j) 的数目。

//class Solution {
//public:
//    int countPairs(vector<int>& nums, int target) {
//        ranges::sort(nums);
//        int ans = 0, left = 0, right = nums.size() - 1;
//        while (left < right) {
//            if (nums[left] + nums[right] < target) {
//                ans += right - left;
//                left++;
//            }
//            else {
//                right--;
//            }
//        }
//
//        return ans;
//    }
//};

//2563.统计公平数对的数目

//给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和两个整数 lower 和 upper ，返回 公平数对的数目 。
//如果(i, j) 数对满足以下情况，则认为它是一个 公平数对 ：
//0 <= i < j < n，且
//lower <= nums[i] + nums[j] <= upper

//class Solution {
//public:
//    long long countFairPairs(vector<int>& nums, int lower, int upper) {
//        ranges::sort(nums);
//
//        auto count = [&](int upper) {
//            long long res = 0;
//            int j = nums.size() - 1;
//            for (int i = 0; i < nums.size(); i++) {
//                while (j > i && nums[j] > upper - nums[i]) {
//                    j--;
//                }
//                if (j == i) {
//                    break;
//                }
//                res += j - i;
//            }
//            return res;
//            };
//
//        return count(upper) - count(lower - 1);
//    }
//};

//LCP 28.采购方案

//小力将 N 个零件的报价存于数组 nums。小力预算为 target，假定小力仅购买两个零件，要求购买零件的花费不超过预算，请问他有多少种采购方案。
//注意：答案需要以 1e9 + 7 (1000000007) 为底取模，如：计算初始结果为：1000000008，请返回 1

//class Solution {
//    int mod = 1e9 + 7;
//public:
//    int purchasePlans(vector<int>& nums, int target) {
//        ranges::sort(nums);
//        int l = 0, r = nums.size() - 1, ans = 0;
//        while (l < r) {
//            while (l < r && nums[l] + nums[r] > target) {
//                r--;
//            }
//            ans += r - l;
//            ans %= mod;
//            l++;
//        }
//
//        return ans;
//    }
//};

//15.三数之和

//给你一个整数数组 nums ，判断是否存在三元组[nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，
//同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
//注意：答案中不可以包含重复的三元组。

//class Solution {
//public:
//    vector<vector<int>> threeSum(vector<int>& nums) {
//        ranges::sort(nums);
//        vector<vector<int>> ans;
//        int n = nums.size();
//        for (int i = 0; i < n - 2; i++) {
//            int x = nums[i];
//            if (i && x == nums[i - 1]) continue;
//            if (x + nums[i + 1] + nums[i + 2] > 0) break;
//            if (x + nums[n - 2] + nums[n - 1] < 0) continue;
//            int j = i + 1, k = n - 1;
//            while (j < k) {
//                int s = x + nums[j] + nums[k];
//                if (s > 0) {
//                    k--;
//                }
//                else if (s < 0) {
//                    j++;
//                }
//                else {
//                    ans.push_back({ x, nums[j], nums[k] });
//                    for (j++; j < k && nums[j] == nums[j - 1]; j++);
//                    for (k--; k > j && nums[k] == nums[k + 1]; k--);
//                }
//            }
//        }
//
//        return ans;
//    }
//};

//16.最接近的三数之和

//给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
//返回这三个数的和。
//假定每组输入只存在恰好一个解。

//class Solution {
//public:
//    int threeSumClosest(vector<int>& nums, int target) {
//        ranges::sort(nums);
//        int ans, n = nums.size();
//        int min_diff = INT_MAX;
//        for (int i = 0; i < n - 2; i++) {
//            int x = nums[i];
//            if (i > 0 && x == nums[i - 1]) {
//                continue;
//            }
//
//            int s = x + nums[i + 1] + nums[i + 2];
//            if (s > target) {
//                if (s - target < min_diff) {
//                    ans = s;
//                }
//                break;
//            }
//
//            s = x + nums[n - 2] + nums[n - 1];
//            if (s < target) {
//                if (target - s < min_diff) {
//                    min_diff = target - s;
//                    ans = s;
//                }
//                continue;
//            }
//
//            int j = i + 1, k = n - 1;
//            while (j < k) {
//                s = x + nums[j] + nums[k];
//                if (s == target) {
//                    return target;
//                }
//                if (s > target) {
//                    if (s - target < min_diff) {
//                        min_diff = s - target;
//                        ans = s;
//                    }
//                    k--;
//                }
//                else {
//                    if (target - s < min_diff) {
//                        min_diff = target - s;
//                        ans = s;
//                    }
//                    j++;
//                }
//            }
//        }
//        return ans;
//    }
//};

//18.四数之和

//给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。
//请你找出并返回满足下述全部条件且不重复的四元组[nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
//0 <= a, b, c, d < n
//a、b、c 和 d 互不相同
//nums[a] + nums[b] + nums[c] + nums[d] == target
//你可以按 任意顺序 返回答案 。

//class Solution {
//public:
//    vector<vector<int>> fourSum(vector<int>& nums, int target) {
//        ranges::sort(nums);
//        vector<vector<int>> ans;
//        int n = nums.size();
//        for (int a = 0; a < n - 3; a++) {
//            long long x = nums[a];
//            if (a > 0 && x == nums[a - 1]) continue;
//            if (x + nums[a + 1] + nums[a + 2] + nums[a + 3] > target) break;
//            if (x + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) continue;
//            for (int b = a + 1; b < n - 2; b++) {
//                long long y = nums[b];
//                if (b > a + 1 && y == nums[b - 1]) continue;
//                if (x + y + nums[b + 1] + nums[b + 2] > target) break;
//                if (x + y + nums[n - 2] + nums[n - 1] < target) continue;
//                int c = b + 1, d = n - 1;
//                while (c < d) {
//                    long long s = x + y + nums[c] + nums[d];
//                    if (s > target) d--;
//                    else if (s < target) c++;
//                    else {
//                        ans.push_back({ (int)x, (int)y, nums[c], nums[d] });
//                        for (c++; c < d && nums[c] == nums[c - 1]; c++);
//                        for (d--; d > c && nums[d] == nums[d + 1]; d--);
//                    }
//                }
//            }
//        }
//        return ans;
//    }
//};

//611.有效三角形的个数

//给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

//class Solution {
//public:
//    int triangleNumber(vector<int>& nums) {
//        ranges::sort(nums);
//        int ans = 0;
//        for (int k = 2; k < nums.size(); k++) {
//            int c = nums[k];
//            int i = 0;
//            int j = k - 1;
//            while (i < j) {
//                if (nums[i] + nums[j] > c) {
//                    ans += j - i;
//                    j--;
//                }
//                else {
//                    i++;
//                }
//            }
//        }
//
//        return ans;
//    }
//};

//1577.数的平方等于两数乘积的方法数

//给你两个整数数组 nums1 和 nums2 ，请你返回根据以下规则形成的三元组的数目（类型 1 和类型 2 ）：
//类型 1：三元组(i, j, k) ，如果 nums1[i]2 == nums2[j] * nums2[k] 其中 0 <= i < nums1.length 且 0 <= j < k < nums2.length
//类型 2：三元组(i, j, k) ，如果 nums2[i]2 == nums1[j] * nums1[k] 其中 0 <= i < nums2.length 且 0 <= j < k < nums1.length

//class Solution {
//public:
//    int numTriplets(vector<int>& nums1, vector<int>& nums2) {
//        ranges::sort(nums1);
//        ranges::sort(nums2);
//        int ans = 0;
// 
//        auto func = [&ans](vector<int>& n1, vector<int>& n2) {
//            long long target, s;
//            int n = n1.size(), m = n2.size();
//            for (int i = n - 1; i >= 0; i--) {
//                target = (long long)n1[i] * n1[i];
//                if (m > 1 && target > (long long)n2[m - 1] * n2[m - 2]) {
//                    continue;
//                }
//                int l = 0, r = m - 1;
//                while (l < r) {
//                    s = (long long)n2[l] * n2[r];
//                    if (s < target) {
//                        l++;
//                    }
//                    else if (s > target) {
//                        r--;
//                    }
//                    else {
//                        if (n2[l] == n2[r]) {
//                            ans += (r - l + 1) * (r - l) / 2;
//                            break;
//                        }
//                        else {
//                            int cnt1 = 0, cnt2 = 0;
//                            int tl = n2[l], tr = n2[r];
//                            while (tl == n2[l]) {
//                                cnt1++;
//                                l++;
//                            }
//                            while (tr == n2[r]) {
//                                cnt2++;
//                                r--;
//                            }
//                            ans += cnt1 * cnt2;
//                        }
//                    }
//                }
//            }
//            };
//        func(nums1, nums2);
//        func(nums2, nums1);
//        return ans;
//    }
//};

//923.三数之和的多种可能

//给定一个整数数组 arr ，以及一个整数 target 作为目标值，返回满足 i < j < k 且 arr[i] + arr[j] + arr[k] == target 的元组 i, j, k 的数量。
//由于结果会非常大，请返回 109 + 7 的模。

//class Solution {
//public:
//    const int mod = 1e9 + 7;
//
//    int threeSumMulti(vector<int>& arr, int target) {
//        int n = arr.size(), ans = 0, sum;
//        ranges::sort(arr);
//
//        for (int i = 0; i < n - 2; i++) {
//            int j = i + 1, k = n - 1, tmp = target - arr[i];
//            while (j < k) {
//                if (arr[j] + arr[k] < tmp) {
//                    j++;
//                }
//                else if (arr[j] + arr[k] > tmp) {
//                    k--;
//                }
//                else {
//                    if (arr[j] == arr[k]) {
//                        ans += (k - j + 1) * (k - j) / 2;
//                        ans %= mod;
//                        break;
//                    }
//                    else {
//                        int l = 0, r = 0;
//                        int tl = arr[j], tr = arr[k];
//                        while (arr[j] == tl) {
//                            l++;
//                            j++;
//                        }
//                        while (arr[k] == tr) {
//                            r++;
//                            k--;
//                        }
//                        ans += l * r;
//                        ans %= mod;
//                    }
//                }
//            }
//        }
//
//        return ans;
//    }
//};

//948.令牌放置

//你的初始 能量 为 power，初始 分数 为 0，只有一包令牌以整数数组 tokens 给出。其中 tokens[i] 是第 i 个令牌的值（下标从 0 开始）。
//你的目标是通过有策略地使用这些令牌以 最大化 总 分数。在一次行动中，你可以用两种方式中的一种来使用一个 未被使用的 令牌（但不是对同一个令牌使用两种方式）：
//朝上：如果你当前 至少 有 tokens[i] 点 能量 ，可以使用令牌 i ，失去 tokens[i] 点 能量 ，并得到 1 分 。
//朝下：如果你当前至少有 1 分 ，可以使用令牌 i ，获得 tokens[i] 点 能量 ，并失去 1 分 。
//在使用 任意 数量的令牌后，返回我们可以得到的最大 分数 。

//class Solution {
//public:
//    int bagOfTokensScore(vector<int>& tokens, int power) {
//        ranges::sort(tokens);
//        int ans = 0, l = 0, r = tokens.size();
//        while (l < r) {
//            if (power >= tokens[l]) {
//                power -= tokens[l];
//                l++;
//                ans++;
//            }
//            else if (ans > 0 && l + 1 < r) {
//                r--;
//                power += tokens[r];
//                ans--;
//            }
//            else {
//                break;
//            }
//        }
//
//        return ans;
//    }
//};

//11.盛最多水的容器

//给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是(i, 0) 和(i, height[i]) 。
//找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
//返回容器可以储存的最大水量。
//说明：你不能倾斜容器。

//class Solution {
//public:
//    int maxArea(vector<int>& height) {
//        int ans = 0, left = 0, right = height.size() - 1;
//        while (left < right) {
//            int area = (right - left) * min(height[left], height[right]);
//            ans = max(ans, area);
//            height[left] < height[right] ? left++ : right--;
//        }
//        return ans;
//    }
//};

//42.接雨水

//给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

//class Solution {
//public:
//    int trap(vector<int>& height) {
//        int ans = 0, pre_max = 0, suf_max = 0;
//        int left = 0, right = height.size() - 1;
//        while (left < right) {
//            pre_max = max(pre_max, height[left]);
//            suf_max = max(suf_max, height[right]);
//            ans += pre_max < suf_max ? pre_max - height[left++] : suf_max - height[right--];
//        }
//
//        return ans;
//    }
//};

//1616.分割两个字符串得到回文串

//给你两个字符串 a 和 b ，它们长度相同。请你选择一个下标，将两个字符串都在 相同的下标 分割开。由 a 可以得到两个字符串： aprefix 和 asuffix ，满足 a = aprefix + asuffix ，
//同理，由 b 可以得到两个字符串 bprefix 和 bsuffix ，满足 b = bprefix + bsuffix 。请你判断 aprefix + bsuffix 或者 bprefix + asuffix 能否构成回文串。
//当你将一个字符串 s 分割成 sprefix 和 ssuffix 时， ssuffix 或者 sprefix 可以为空。比方说， s = "abc" 那么 "" + "abc" ， "a" + "bc" ， "ab" + "c" 和 "abc" + "" 都是合法分割。
//如果 能构成回文字符串 ，那么请返回 true，否则返回 false 。
//注意， x + y 表示连接字符串 x 和 y 。

//class Solution {
//    bool isPalindrome(string& s, int i, int j) {
//        while (i < j && s[i] == s[j])
//            ++i, --j;
//        return i >= j;
//    }
//
//    bool check(string& a, string& b) {
//        int i = 0, j = a.length() - 1;
//        while (i < j && a[i] == b[j])
//            ++i, --j;
//        return isPalindrome(a, i, j) || isPalindrome(b, i, j);
//    }
//
//public:
//    bool checkPalindromeFormation(string& a, string& b) {
//        return check(a, b) || check(b, a);
//    }
//};

//1498.满足条件的子序列数目

//给你一个整数数组 nums 和一个整数 target 。
//请你统计并返回 nums 中能满足其最小元素与最大元素的 和 小于或等于 target 的 非空 子序列的数目。
//由于答案可能很大，请将结果对 109 + 7 取余后返回。

//const int MOD = 1'000'000'007;
//const int MX = 100'000;
//
//int pow2[MX];
//
//auto init = [] {
//    pow2[0] = 1;
//    for (int i = 1; i < MX; i++) {
//        pow2[i] = pow2[i - 1] * 2 % MOD;
//    }
//    return 0;
//    }();
//
//class Solution {
//public:
//    int numSubseq(vector<int>& nums, int target) {
//        ranges::sort(nums);
//        long long ans = 0;
//        int left = 0, right = nums.size() - 1;
//        while (left <= right) {
//            if (nums[left] + nums[right] <= target) {
//                ans += pow2[right - left];
//                left++;
//            }
//            else {
//                right--;
//            }
//        }
//
//        return ans % MOD;
//    }
//};

//1782.统计点对的数目

//给你一个无向图，无向图由整数 n  ，表示图中节点的数目，和 edges 组成，其中 edges[i] = [ui, vi] 表示 ui 和 vi 之间有一条无向边。同时给你一个代表查询的整数数组 queries 。
//第 j 个查询的答案是满足如下条件的点对(a, b) 的数目：
//a < b
//cnt 是与 a 或者 b 相连的边的数目，且 cnt 严格大于 queries[j] 。
//请你返回一个数组 answers ，其中 answers.length == queries.length 且 answers[j] 是第 j 个查询的答案。
//请注意，图中可能会有 多重边 。

//class Solution {
//public:
//    vector<int> countPairs(int n, vector<vector<int>>& edges, vector<int>& queries) {
//        // deg[i] 表示与点 i 相连的边的数目
//        vector<int> deg(n + 1); // 节点编号从 1 到 n
//        unordered_map<int, int> cnt_e;
//        for (auto& e : edges) {
//            int x = e[0], y = e[1];
//            if (x > y) swap(x, y); // 注意 1-2 和 2-1 算同一条边
//            deg[x]++;
//            deg[y]++;
//            // 统计每条边的出现次数
//            cnt_e[x << 16 | y]++; // 用一个 int 存储两个不超过 65535 的数
//        }
//
//        vector<int> ans(queries.size());
//        vector<int> sorted_deg = deg;
//        sort(sorted_deg.begin(), sorted_deg.end()); // 排序，为了双指针
//        for (int j = 0; j < queries.size(); j++) {
//            int q = queries[j];
//            int left = 1, right = n; // 相向双指针
//            while (left < right) {
//                if (sorted_deg[left] + sorted_deg[right] <= q) {
//                    left++;
//                }
//                else {
//                    ans[j] += right - left;
//                    right--;
//                }
//            }
//            for (auto [k, c] : cnt_e) {
//                int s = deg[k >> 16] + deg[k & 0xffff]; // 取出 k 的高 16 位和低 16 位
//                if (s > q && s - c <= q) {
//                    ans[j]--;
//                }
//            }
//        }
//        return ans;
//    }
//};

//1574.删除最短的子数组使剩余数组有序

//给你一个整数数组 arr ，请你删除一个子数组（可以为空），使得 arr 中剩下的元素是 非递减 的。
//一个子数组指的是原数组中连续的一个子序列。
//请你返回满足题目要求的最短子数组的长度。

//class Solution {
//public:
//    int findLengthOfShortestSubarray(vector<int>& arr) {
//        int n = arr.size(), right = n - 1;
//        while (right && arr[right - 1] <= arr[right]) {
//            --right;
//        }
//        if (right == 0) {
//            return 0;
//        }
//        int ans = right;
//        for (int left = 0; left == 0 || arr[left - 1] <= arr[left]; left++) {
//            while (right < n && arr[right] < arr[left]) {
//                right++;
//            }
//            ans = min(ans, right - left - 1);
//        }
//        return ans;
//    }
//};

//2972.统计移除递增子数组的数目 II

//给你一个下标从 0 开始的 正 整数数组 nums 。
//如果 nums 的一个子数组满足：移除这个子数组后剩余元素 严格递增 ，那么我们称这个子数组为 移除递增 子数组。
//比方说，[5, 3, 4, 6, 7] 中的[3, 4] 是一个移除递增子数组，因为移除该子数组后，[5, 3, 4, 6, 7] 变为[5, 6, 7] ，是严格递增的。
//请你返回 nums 中 移除递增 子数组的总数目。
//注意 ，剩余元素为空的数组也视为是递增的。
//子数组 指的是一个数组中一段连续的元素序列。

//class Solution {
//public:
//    long long incremovableSubarrayCount(vector<int>& a) {
//        int n = a.size();
//        int i = 0;
//        while (i < n - 1 && a[i] < a[i + 1]) {
//            i++;
//        }
//        if (i == n - 1) {
//            return (long long)n * (n + 1) / 2;
//        }
//
//        long long ans = i + 2;
//        for (int j = n - 1; j == n - 1 || a[j] < a[j + 1]; j--) {
//            while (i >= 0 && a[i] >= a[j]) {
//                i--;
//            }
//            ans += i + 2;
//        }
//        return ans;
//    }
//};

//2122.还原原数组

//Alice 有一个下标从 0 开始的数组 arr ，由 n 个正整数组成。她会选择一个任意的 正整数 k 并按下述方式创建两个下标从 0 开始的新整数数组 lower 和 higher ：
//对每个满足 0 <= i < n 的下标 i ，lower[i] = arr[i] - k
//对每个满足 0 <= i < n 的下标 i ，higher[i] = arr[i] + k
//不幸地是，Alice 丢失了全部三个数组。但是，她记住了在数组 lower 和 higher 中出现的整数，但不知道每个整数属于哪个数组。请你帮助 Alice 还原原数组。
//给你一个由 2n 个整数组成的整数数组 nums ，其中 恰好 n 个整数出现在 lower ，剩下的出现在 higher ，还原并返回 原数组 arr 。如果出现答案不唯一的情况，返回 任一 有效数组。
//注意：生成的测试用例保证存在 至少一个 有效数组 arr

//class Solution {
//public:
//    vector<int> recoverArray(vector<int>& nums) {
//        ranges::sort(nums);
//        int n = nums.size();
//        for (int i = 1; i < n; i++) {
//            if (nums[i] == nums[i - 1]) {
//                continue;
//            }
//            int d = nums[i] - nums[0];
//            if ((d & 1) > 0) {
//                continue;
//            }
//            int k = d / 2;
//            vector<int8_t> vis(n);
//            vis[i] = true;
//            vector<int> ans{ nums[i] - k };
//
//            int l = 1, r = i + 1;
//            while (r < n) {
//                while (l < n - 1 && vis[l]) {
//                    l++;
//                }
//                while (r < n && nums[r] - nums[l] < d) {
//                    r++;
//                }
//                if (r == n || nums[r] - nums[l] > d) {
//                    break;
//                }
//                vis[r] = true;
//                ans.emplace_back(nums[r] - k);
//                r++;
//                l++;
//            }
//            if (ans.size() == n / 2) {
//                return ans;
//            }
//        }
//        return {};
//    }
//};

//2234.花园的最大总美丽值

//Alice 是 n 个花园的园丁，她想通过种花，最大化她所有花园的总美丽值。
//给你一个下标从 0 开始大小为 n 的整数数组 flowers ，其中 flowers[i] 是第 i 个花园里已经种的花的数目。已经种了的花 不能 移走。
//同时给你 newFlowers ，表示 Alice 额外可以种花的 最大数目 。同时给你的还有整数 target ，full 和 partial 。
//如果一个花园有 至少 target 朵花，那么这个花园称为 完善的 ，花园的 总美丽值 为以下分数之 和 ：
//完善 花园数目乘以 full.
//剩余 不完善 花园里，花的 最少数目 乘以 partial 。如果没有不完善花园，那么这一部分的值为 0 。
//请你返回 Alice 种最多 newFlowers 朵花以后，能得到的 最大 总美丽值。

//class Solution {
//public:
//    long long maximumBeauty(vector<int>& flowers, long long newFlowers, int target, int full, int partial) {
//        int n = flowers.size();
//        long long left_flowers = newFlowers - 1ll * target * n;
//        for (int& flower : flowers) {
//            flower = min(flower, target);
//            left_flowers += flower;
//        }
//
//        if (left_flowers == newFlowers) {
//            return 1ll * n * full;
//        }
//        if (left_flowers >= 0) {
//            return max(1ll * (target - 1) * partial + 1ll * (n - 1) * full, 1ll * n * full);
//        }
//
//        ranges::sort(flowers);
//        long long ans = 0, pre_sum = 0;
//        int j = 0;
//        for (int i = 1; i <= n; i++) {
//            left_flowers += target - flowers[i - 1];
//            if (left_flowers < 0) {
//                continue;
//            }
//            while (j < i && 1ll * flowers[j] * j <= pre_sum + left_flowers) {
//                pre_sum += flowers[j];
//                j++;
//            }
//            long long avg = (pre_sum + left_flowers) / j;
//            long long total_beauty = avg * partial + 1ll * (n - i) * full;
//            ans = max(ans, total_beauty);
//        }
//        return ans;
//    }
//};

//581.最短无序连续子数组

//给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
//请你找出符合题意的 最短 子数组，并输出它的长度。

//class Solution {
//public:
//    int findUnsortedSubarray(vector<int>& nums) {
//        int n = nums.size();
//        int maxn = INT_MIN, right = -1;
//        int minn = INT_MAX, left = -1;
//        for (int i = 0; i < n; i++) {
//            if (maxn > nums[i]) {
//                right = i;
//            }
//            else {
//                maxn = nums[i];
//            }
//            if (minn < nums[n - i - 1]) {
//                left = n - i - 1;
//            }
//            else {
//                minn = nums[n - i - 1];
//            }
//        }
//        return right == -1 ? 0 : right - left + 1;
//    }
//};

//1793.好子数组的最大分数

//给你一个整数数组 nums （下标从 0 开始）和一个整数 k 。
//一个子数组(i, j) 的 分数 定义为 min(nums[i], nums[i + 1], ..., nums[j]) * (j - i + 1) 。一个 好 子数组的两个端点下标需要满足 i <= k <= j 。
//请你返回 好 子数组的最大可能 分数 。

//class Solution {
//public:
//    int maximumScore(vector<int>& nums, int k) {
//        int n = nums.size();
//        int ans = nums[k], min_h = nums[k];
//        int i = k, j = k;
//        for (int t = 0; t < n - 1; t++) {
//            if (j == n - 1 || i && nums[i - 1] > nums[j + 1]) {
//                min_h = min(min_h, nums[--i]);
//            }
//            else {
//                min_h = min(min_h, nums[++j]);
//            }
//            ans = max(ans, min_h * (j - i + 1));
//        }
//        return ans;
//    }
//};

//27.移除元素

//给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
//假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：
//更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
//返回 k。

//class Solution {
//public:
//    int removeElement(vector<int>& nums, int val) {
//        int left = 0;
//        for (int x : nums) {
//            if (x != val) {
//                nums[left++] = x;
//            }
//        }
//        return left;
//    }
//};

//26.删除有序数组中的重复项

//给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
//元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
//考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
//更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
//返回 k 。

//class Solution {
//public:
//    int removeDuplicates(vector<int>& nums) {
//        int k = 1;
//        for (int i = 1; i < nums.size(); i++) {
//            if (nums[i] != nums[i - 1]) { // nums[i] 不是重复项
//                nums[k++] = nums[i]; // 保留 nums[i]
//            }
//        }
//        return k;
//    }
//};

//80.删除有序数组中的重复项 II

//给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。
//不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

//class Solution {
//public:
//    int removeDuplicates(vector<int>& nums) {
//        int k = 2, n = nums.size();
//        for (int i = 2; i < n; i++) {
//            if (nums[i] != nums[k - 2]) {
//                nums[k++] = nums[i];
//            }
//        }
//        return min(k, n);
//    }
//};

//283.移动零

//给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
//请注意 ，必须在不复制数组的情况下原地对数组进行操作。

//class Solution {
//public:
//    void moveZeroes(vector<int>& nums) {
//        int l = 0, n = nums.size();
//        for (int r = 0; r < n; r++) {
//            if (nums[r]) {
//                nums[l] = nums[r];
//                l++;
//            }
//        }
//
//        for (; l < n; l++) {
//            nums[l] = 0;
//        }
//    }
//};

//905.按奇偶排序数组

//给你一个整数数组 nums，将 nums 中的的所有偶数元素移动到数组的前面，后跟所有奇数元素。
//返回满足此条件的 任一数组 作为答案。

//class Solution {
//public:
//    vector<int> sortArrayByParity(vector<int>& nums) {
//        int l = 0, r = nums.size() - 1;
//        while (l < r) {
//            while (l < r && (nums[l] & 1) == 0) {
//                l++;
//            }
//            while (l < r && nums[r] & 1) {
//                r--;
//            }
//            swap(nums[l], nums[r]);
//            l++;
//            r--;
//        }
//
//        return nums;
//    }
//};

//922.按奇偶排序数组 II

//给定一个非负整数数组 nums，  nums 中一半整数是 奇数 ，一半整数是 偶数 。
//对数组进行排序，以便当 nums[i] 为奇数时，i 也是 奇数 ；当 nums[i] 为偶数时， i 也是 偶数 。
//你可以返回 任何满足上述条件的数组作为答案 。

//class Solution {
//public:
//    vector<int> sortArrayByParityII(vector<int>& nums) {
//        int i = 0, j = 1, n = nums.size();
//        while (i < n) {
//            if (nums[i] % 2 == 0) {
//                i += 2;
//            }
//            else if (nums[j] % 2 == 1) {
//                j += 2;
//            }
//            else {
//                swap(nums[i], nums[j]);
//                i += 2;
//                j += 2;
//            }
//        }
//        return nums;
//    }
//};

//3467.将数组按照奇偶性转化

//给你一个整数数组 nums。请你按照以下顺序 依次 执行操作，转换 nums：
//将每个偶数替换为 0。
//将每个奇数替换为 1。
//按 非递减 顺序排序修改后的数组。
//执行完这些操作后，返回结果数组。

//class Solution {
//public:
//    vector<int> transformArray(vector<int>& nums) {
//        int l = 0, n = nums.size();
//        for (int r = 0; r < n; r++) {
//            if ((nums[r] & 1) == 0) {
//                nums[l++] = 0;
//            }
//        }
//
//        for (; l < n; l++) {
//            nums[l] = 1;
//        }
//        return nums;
//    }
//};

//2460.对数组执行操作

//给你一个下标从 0 开始的数组 nums ，数组大小为 n ，且由 非负 整数组成。
//你需要对数组执行 n - 1 步操作，其中第 i 步操作（从 0 开始计数）要求对 nums 中第 i 个元素执行下述指令：
//如果 nums[i] == nums[i + 1] ，则 nums[i] 的值变成原来的 2 倍，nums[i + 1] 的值变成 0 。否则，跳过这步操作。
//在执行完 全部 操作后，将所有 0 移动 到数组的 末尾 。
//例如，数组[1, 0, 2, 0, 0, 1] 将所有 0 移动到末尾后变为[1, 2, 1, 0, 0, 0] 。
//返回结果数组。
//注意 操作应当 依次有序 执行，而不是一次性全部执行。

//class Solution {
//public:
//    vector<int> applyOperations(vector<int>& nums) {
//        int l = 0, n = nums.size();
//        for (int r = 0; r < n - 1; r++) {
//            if (nums[r]) {
//                if (nums[r] == nums[r + 1]) {
//                    nums[r] *= 2;
//                    nums[r + 1] = 0;
//                }
//                nums[l++] = nums[r];
//            }
//        }
//
//        if (nums[n - 1]) {
//            nums[l++] = nums[n - 1];
//        }
//        for (; l < n; l++) {
//            nums[l] = 0;
//        }
//        return nums;
//    }
//};

//1089.复写零

//给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。
//注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。

//class Solution {
//public:
//    void duplicateZeros(vector<int>& arr) {
//        int l = 0, n = arr.size(), r = n - 1, end = n - 1;
//        for (; l < r; l++) {
//            if (arr[l] == 0) {
//                r--;
//            }
//        }
//        if (l == r && arr[l] == 0) {
//            arr[end--] = arr[r--];
//        }
//        while (r >= 0) {
//            if (arr[r] == 0) {
//                arr[end--] = 0;
//            }
//            arr[end--] = arr[r--];
//        }
//    }
//};

//75.颜色分类

//给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
//我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
//必须在不使用库内置的 sort 函数的情况下解决这个问题。

//class Solution {
//public:
//    void sortColors(vector<int>& nums) {
//        int n = nums.size();
//        int p0 = 0, p2 = n - 1;
//        for (int i = 0; i <= p2; ++i) {
//            while (i <= p2 && nums[i] == 2) {
//                swap(nums[i], nums[p2]);
//                --p2;
//            }
//            if (nums[i] == 0) {
//                swap(nums[i], nums[p0]);
//                ++p0;
//            }
//        }
//    }
//};

//1920.基于排列构建数组

//给你一个 从 0 开始的排列 nums（下标也从 0 开始）。请你构建一个 同样长度 的数组 ans ，其中，对于每个 i（0 <= i < nums.length），都满足 ans[i] = nums[nums[i]] 。
//返回构建好的数组 ans 。
//从 0 开始的排列 nums 是一个由 0 到 nums.length - 1（0 和 nums.length - 1 也包含在内）的不同整数组成的数组。

//class Solution {
//public:
//    vector<int> buildArray(vector<int>& nums) {
//        for (int i = 0; i < nums.size(); i++) {
//            int x = nums[i];
//            if (x < 0) { // 已搬家
//                continue;
//            }
//            int cur = i;
//            while (nums[cur] != i) {
//                int nxt = nums[cur];
//                nums[cur] = ~nums[nxt]; // 把下一个数搬过来，同时做标记（取反）
//                cur = nxt;
//            }
//            nums[cur] = ~x; // 对于这一组的最后一个数，把起点 x=nums[i] 搬过来
//        }
//
//        for (int i = 0; i < nums.size(); i++) {
//            nums[i] = ~nums[i]; // 复原
//        }
//        return nums;
//    }
//};

//442.数组中重复的数据

//给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围[1, n] 内，且每个整数出现 最多两次 。请你找出所有出现 两次 的整数，并以数组形式返回。
//你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间（不包括存储输出所需的空间）的算法解决此问题。

//class Solution {
//public:
//    vector<int> findDuplicates(vector<int>& nums) {
//        int n = nums.size();
//        for (int i = 0; i < n; ++i) {
//            while (nums[i] != nums[nums[i] - 1]) {
//                swap(nums[i], nums[nums[i] - 1]);
//            }
//        }
//        vector<int> ans;
//        for (int i = 0; i < n; ++i) {
//            if (nums[i] - 1 != i) {
//                ans.push_back(nums[i]);
//            }
//        }
//        return ans;
//    }
//};

//448.找到所有数组中消失的数字

//给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间[1, n] 内。请你找出所有在[1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

//class Solution {
//public:
//    vector<int> findDisappearedNumbers(vector<int>& nums) {
//        int n = nums.size();
//        for (int i = 0; i < n; ++i) {
//            while (nums[i] != nums[nums[i] - 1]) {
//                swap(nums[i], nums[nums[i] - 1]);
//            }
//        }
//        vector<int> ans;
//        for (int i = 0; i < n; ++i) {
//            if (nums[i] != i + 1) {
//                ans.push_back(i + 1);
//            }
//        }
//        return ans;
//    }
//};

//41.缺失的第一个正数

//给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
//请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

//class Solution {
//public:
//    int firstMissingPositive(vector<int>& nums) {
//        int n = nums.size();
//        for (int i = 0; i < n; i++) {
//            while (1 <= nums[i] && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
//                int j = nums[i] - 1;
//                swap(nums[i], nums[j]);
//            }
//        }
//
//        for (int i = 0; i < n; i++) {
//            if (nums[i] != i + 1) {
//                return i + 1;
//            }
//        }
//        return n + 1;
//    }
//};

//287.寻找重复数

//给定一个包含 n + 1 个整数的数组 nums ，其数字都在[1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
//假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
//你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

//class Solution {
//public:
//    int findDuplicate(vector<int>& nums) {
//        int fast = 0, slow = 0;
//        while (true) {
//            fast = nums[nums[fast]];
//            slow = nums[slow];
//            if (fast == slow)
//                break;
//        }
//        int finder = 0;
//        while (true) {
//            finder = nums[finder];
//            slow = nums[slow];
//            if (slow == finder)
//                break;
//        }
//        return slow;
//    }
//};